package ru.susu.algebra.ranks;

import java.io.BufferedOutputStream;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Date;
import java.util.Map;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import ru.susu.algebra.number.MapPrimeNumbersProvider;
import ru.susu.algebra.util.StringUtilities;

/**
 * Строит нужные разбиения рекурсивно.
 * Проверяет гипотезу о том, что разбиение являющееся квадратом всегда сравнимо по модулю 4 с n. (проверено до 200)
 *
 * @author akargapolov
 * @since: 10.03.2011
 */
public class FullRecRanksCounter
{
	private static Logger _logger = Logger.getLogger("ranks");

	private static int NUMBER = 200;
	private static int WIDTH = 30;
	private static int MOD = 8;

	private static Map<Integer, BitSet> _factors = new NumbersBitSetFactorizationProvider().performOperation(NUMBER);
	private static Map<Integer, Integer> _primes = new MapPrimeNumbersProvider().performOperation(NUMBER);
	private static int[][] _dp = new int[NUMBER + 1][NUMBER + 1];
	private static int[] _numbers = new int[NUMBER + 1];

	private static Map<Integer, BigInteger[]> _result = Maps.newHashMap();

	public static void main(String[] args) throws Exception
	{
		BasicConfigurator.configure();

		StringBuilder builder = new StringBuilder();
		builder.append(StringUtilities.toString("n", WIDTH)).append(StringUtilities.toString("ранг", WIDTH)).append(
				StringUtilities.toString("квадр", WIDTH)).append("\n");

		for (int start = 1; start <= MOD; start++)
		{
			for (int n = start; n <= NUMBER; n+=MOD)
			{
				Date startTime = new Date();
				BigInteger[] value = new BigInteger[2];
				Arrays.fill(value, BigInteger.ZERO);
				_result.put(n, value);
				rec(n, 1, 0, 0, new BitSet(_primes.size()));
				Date end = new Date();
				_logger.info(n + " executing time: " + (end.getTime() - startTime.getTime()) + "ms");
				_logger.info(Lists.newArrayList(value));
				builder.append(StringUtilities.toString(n, WIDTH)).append(
						StringUtilities.toString(value[0].toString(), WIDTH)).append(
						StringUtilities.toString(value[1].toString(), WIDTH)).append("\n");
			}
		}

		OutputStream os = new BufferedOutputStream(new FileOutputStream("Ranks/RecRank" + NUMBER + "_" + MOD + ".txt"));
		//os.write(builder.toString().getBytes("cp1251"));
		os.write(builder.toString().getBytes("utf8"));
		os.flush();
		os.close();
	}

	private static void rec(int n, int k, int sum, int length, BitSet bitset)
	{
		if (n == sum)
		{
			if (length % 4 != n % 4)
			{
				if (bitset.isEmpty())
					throw new RuntimeException("Квадрат не сравним по модулю 4!!!");
				return;
			}

			BigInteger[] value = _result.get(n);
			if (bitset.isEmpty())
				value[1] = value[1].add(BigInteger.ONE);
			else
				value[0] = value[0].add(BigInteger.ONE);

			return;
		}
		if (k > n || sum > n)
			return;

		if (recDP(n - sum - k, k + 2) == 1)
		{
			_numbers[length] = k;
			BitSet tmp = (BitSet) bitset.clone();
			tmp.xor(_factors.get(k));
			rec(n, k + 2, sum + k, length + 1, tmp);
			_numbers[length] = 0;
		}

		if (recDP(n - sum, k + 2) == 1)
		{
			rec(n, k + 2, sum, length, bitset);
		}
	}

	private static int recDP(int n, int k)
	{
		if (n == 0)
			return 1;
		if (k > n)
			return -1;
		if (_dp[n][k] != 0)
			return _dp[n][k];

		int res = -1;

		if (recDP(n - k, k + 2) == 1 || recDP(n, k + 2) == 1)
			res = 1;

		_dp[n][k] = res;
		return res;
	}

}
